// 6.37 试利用栈的基本操作写出先序遍历的非递归形式的算法。
// 6.38 同6.37题条件，写出后序遍历的非递归算法（提示：为分辨后序遍历时两次进栈的不同返回点，需在指针进栈时同时将一个标志进栈）。

#include <stdio.h>
#include <stdlib.h>
#include "E:\Desktop\data_struct\5TREE\1_bin_tree\creat.h"
void fun_6_37(tree *root)
{
    tree *stack[100];
    int top = -1;
    tree *p = root;
    while (p || top >= 0)
    {
        while (p)
        {
            stack[++top] = p;
            printf("%3d", p->data);
            p = p->left;
        }
        if (top >= 0)
        {
            p = stack[top--]->right;
        }
    }
    printf("\n");
}
void fun_6_38(tree *root)
{
    tree *stack[100];
    int top = -1;
    int flag[100] = {0};
    tree *p = root;
    while (p || top >= 0)
    {
        while (p)
        {
            stack[++top] = p;
            flag[top]++;
            p = p->left;
        }
        switch (flag[top])
        {
        case 1:
            if (stack[top]->right)
                p = stack[top]->right;
            flag[top]++;
            break;
        case 2:
            printf("%3d", stack[top]->data);
            flag[top] = 0;
            top--;
            break;
        default:
            break;
        }
    }
}

int main()
{
    /*******************code*******************/
    int n = 15;
    int a[15] = {1,
                 2, 3,
                 4, 5, NULL, NULL,
                 NULL, 6, 7, NULL, NULL, NULL, NULL, NULL};
    tree *root;
    CreatTree(root, a, n, 0);
    fun_6_37(root);
    fun_6_38(root);
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
